evalDC :: Eq a => (a -> Bool) -> (a -> b) -> (a -> [a]) -> ([b] -> b) -> a -> b
evalDC isBase base split join x | isBase x = base x
				| otherwise = join (map (evalDC isBase base split join) (split x))

subsecuencia :: (Eq a) => ([a],[a]) -> Bool
subsecuencia (x,y) = evalDC isBase base split join (x,y)

base:: (Eq a) => ([a],[a]) -> Bool
base (xs,ys) = iguales xs ys

iguales:: (Eq a) => [a] -> [a] -> Bool
iguales [] _ = True
iguales (x:xs) [] = False
iguales (x:xs) (y:ys) = (x == y) && (iguales xs ys)

isBase:: (Eq a) => ([a],[a]) -> Bool
isBase (xs,ys) = xs == [] || ys == [] || length(xs) == length(ys)

split:: (Eq a) => ([a],[a]) -> [([a],[a])]
split (xs,(y:ys)) =[(xs,ys),(xs,(init(y:ys)))]

join:: [Bool] -> Bool 
join [] = False
join (x:xs) = x || join xs

evalDP :: Eq a => (a -> Bool) -> (a -> b) -> (a -> [a]) -> ([b] -> b) -> a -> b
evalDP isBase base split join x = solution x (evalDPStore isBase base split join x [])

evalDPStore :: Eq a => (a -> Bool) -> (a -> b) -> (a -> [a]) -> ([b] -> b) -> a -> [(a,b)] -> [(a,b)]
evalDPStore isBase base split join x cache | solved x cache = cache
					   					   | isBase x = (x,(base x)):cache
					                       | otherwise = ((head(split x)):cache1):((last(split x)):cache2)
	where 
		cache1 = evalDPStore isBase base split join (head(split x)) cache
		sol1 = solution (head(split x)) (cache1)
		cache2 = evalDPStore isBase base split join (last(split x)) cache1
		sol2 = solution (last(split x)) (cache2)
		--tupla1 = (x,head(split x))
		--tupla2 = (x,last(split x))

solution :: Eq a => a -> [(a,b)] -> b
solution x (y:ys)
	| x == (fst y) = snd y
	| otherwise = solution x ys

solved :: Eq a => a -> [(a,b)] -> Bool
solved x [] = False
solved x (y:ys) = (x == fst y) || solved x ys 

subsecuenciaMemo :: (Eq a) => ([a],[a]) -> Bool
subsecuenciaMemo (x,y) = evalDP isBase base split join (x,y)

	
